# 思路：转换成两个树是否互为镜像
# 队列每次插入的为左树的左子树，右树的右子树，左树的右子树，右树的左子树
from collections import deque
from tools.treeNode import Tree


def isSymmetric(root):
    return check(root, root)


def check(p, q):
    if (not p) and (not q):
        return True
    if (not p) or (not q):
        return False
    que = deque()
    que.append(p)
    que.append(q)
    while len(que):
        a = que.popleft()
        b = que.popleft()
        if (not a) and (not b):
            continue
        if (not a) or (not b):
            return False
        if a.val != b.val:
            return False
        que.append(a.left)
        que.append(b.right)
        que.append(a.right)
        que.append(b.left)
    return len(que) == 0


root = Tree(1)
root.left = Tree(2)
root.right = Tree(2)
root.left.left = Tree(3)
root.left.right = Tree(4)
root.right.left = Tree(4)
root.right.right = Tree(3)
print(isSymmetric(root))  # True
